package com.dzu.hard;

/**
 * @author ZhaoDong
 * @date 2022/11/3 9:59
 * @description 214. 最短回文串
 */
public class Test214 {
    public static void main(String[] args) {

        // s：
        System.out.println(shortestPalindromeByKMP2("aacecaaa"));
    }

    // abcd  dcba  acbabcd
    public static String shortestPalindrome(String s) {
        String reverse = new StringBuffer(s).reverse().toString();
        for (int i = s.length(); i >= 0; i--) {
            if (s.substring(0, i).equals(reverse.substring(s.length() - i))) {
                return reverse.substring(0, s.length() - i) + s;
            }
        }
        return s;
    }


    /**
     * https://leetcode.cn/problems/shortest-palindrome/solution/shou-hua-tu-jie-cong-jian-dan-de-bao-li-fa-xiang-d/
     *
     * 通过next数组得到 s 和 reverse_s 的最大公共前后缀的长度，
     * @param s
     * @return
     */
    public static String shortestPalindromeByKMP(String s) {
        String reverse = new StringBuffer(s).reverse().toString();
        String newS = s + "#" + reverse;

        int length = newS.length();
        int[] next = new int[length];
        for (int i = 1, j = 0; i < length; i++) {
            while (j > 0 && newS.charAt(i) != newS.charAt(j)) {
                j = next[j - 1];
            }
            if (newS.charAt(i) == newS.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        int count = next[length - 1];

        return reverse.substring(0, reverse.length() - count) + s;

    }


    /**
     * fast
     *  同理： 求出s 和 reverse_s 的最大公共前后缀。
     *  没使用sb的api，而是通过逆序遍历，每次匹配相同j++,最总j的个数就是s和reverse_s的最大公共前缀的长度，然后截取+取反+拼接
     * @param s
     * @return
     */
    public static String shortestPalindromeByKMP2(String s) {

        int length = s.length();
        int[] next = new int[length];
        for (int i = 1, j = 0; i < length; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        int j = 0;
        for (int i = length - 1; i >=0; i--) {

            while (j > 0 && s.charAt(j) != s.charAt(i)) {
                j = next[j - 1];
            }
            if (s.charAt(j) == s.charAt(i)) {
                j++;
            }
        }

        String add = (j == length ? "" : s.substring(j));

        StringBuffer ans = new StringBuffer(add).reverse();
        ans.append(s);
        return ans.toString();

    }
}
